//
// Description: 725. 分隔链表
// Created by Loading on 2021/9/22.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>

using namespace std;

vector<ListNode *> splitListToParts(ListNode *head, int k) {
    vector<ListNode *> res;
    // 链表长度
    int len = 0;
    ListNode *root = head;
    while (root) {
        ++len;
        root = root->next;
    }
    // 链表为空
    if (len == 0) {
        while (k--) {
            res.emplace_back(nullptr);
        }

        return res;
    }

    // 平均分配后子链表最短长度，剩余长度
    int per_len = len / k, remain = len % k;

    while (k--) {
        res.emplace_back(head);
        int l = per_len - 1;
        // 如果还有剩余长度，从前往后子链表，长度 + 1
        if (remain-- > 0) {
            l++;
        }
        // 仍存在下一个子链表
        if (head) {
            while (l--) {
                head = head->next;
            }
            ListNode *temp = head->next;
            head->next = nullptr;
            head = temp;
        }
    }

    return res;
}

int main() {
    auto head = new ListNode(1);
    auto root = head;
    for (int i = 2; i <= 10; ++i) {
        head->next = new ListNode(i);
        head = head->next;
    }
    int k = 3;
    vector<ListNode *> res = splitListToParts(root, k);
    for (auto &l : res) {
        if (!l) {
            cout << "nullptr" << endl;
        } else {
            while (l) {
                cout << l->val << " ";
                auto temp = l;
                l = l->next;
                delete temp;
            }
            cout << endl;
        }
    }

    return 0;
}